package top.minuy.subject.leetcode._773;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * 773. 滑动谜题
 * 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
 * <p>
 * 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
 * <p>
 * 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
 * <p>
 * 给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
 * <p>
 * 示例：
 * <p>
 * 输入：board = [[1,2,3],[4,0,5]]
 * 输出：1
 * 解释：交换 0 和 5 ，1 步完成
 * 输入：board = [[1,2,3],[5,4,0]]
 * 输出：-1
 * 解释：没有办法完成谜板
 * 输入：board = [[4,1,2],[5,0,3]]
 * 输出：5
 * 解释：
 * 最少完成谜板的最少移动次数是 5 ，
 * 一种移动路径:
 * 尚未移动: [[4,1,2],[5,0,3]]
 * 移动 1 次: [[4,1,2],[0,5,3]]
 * 移动 2 次: [[0,1,2],[4,5,3]]
 * 移动 3 次: [[1,0,2],[4,5,3]]
 * 移动 4 次: [[1,2,0],[4,5,3]]
 * 移动 5 次: [[1,2,3],[4,5,0]]
 * 输入：board = [[3,2,4],[1,5,0]]
 * 输出：14
 * 提示：
 * <p>
 * board 是一个如上所述的 2 x 3 的数组.
 * board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.
 * 通过次数23,941提交次数33,665
 *
 * @author Minuy
 * @time 12:30
 * @date 2021/11/21
 */
public class Solution {
    int s, t;
    int[][] dir4 = {
            {-1, 0},
            {0, -1}, {0, 1},
            {1, 0}
    };

    public int slidingPuzzle(int[][] board) {
        t = 123450;
        s = boardToInt(board);

        if (s == t) {
            return 0;
        }

        HashMap<Integer, Integer> disVisited = new HashMap<>();

        int sta = s;
        int dis = 0;
        ArrayList<Integer> queue = new ArrayList<>();
        queue.add(sta);
        disVisited.put(sta, dis);
        while (!queue.isEmpty()) {
            sta = queue.remove(0);
            dis = disVisited.get(sta);

            ArrayList<Integer> nextSta = getNextSta(sta);

            for (Integer curSta : nextSta) {
                if (!disVisited.containsKey(curSta)) {
                    queue.add(curSta);
                    disVisited.put(curSta, dis + 1);

                    if (curSta == t) {
                        return disVisited.get(t);
                    }
                }
            }
        }

        return -1;
    }

    private ArrayList<Integer> getNextSta(int sta) {
        int[][] board = intToBoard(sta);
        ArrayList<Integer> nextSta = new ArrayList<>();
        int x = 0, y = 0;
        boolean isFind = false;
        for (x = 0; x < board.length; x++) {
            for (y = 0; y < board[x].length; y++) {
                if (board[x][y] == 0) {
                    isFind = true;
                    break;
                }
            }
            if (isFind) {
                break;
            }
        }
        int x1, y1;
        for (int[] ints : dir4) {
            x1 = x + ints[0];
            y1 = y + ints[1];
            if (x1 >= 0 && y1 >= 0 && x1 < board.length && y1 < board[0].length) {
                swap(board, x, y, x1, y1); // 移动
                nextSta.add(boardToInt(board)); // 添加下一个状态
                swap(board, x, y, x1, y1); // 还原
            }
        }
        return nextSta;
    }

    private void swap(int[][] b, int x1, int y1, int x2, int y2) {
        int t = b[x2][y2];
        b[x2][y2] = b[x1][y1];
        b[x1][y1] = t;
    }

    private int boardToInt(int[][] board) {
        int res = 0;
        res += board[1][2];
        res += board[1][1] * 10;
        res += board[1][0] * 100;
        res += board[0][2] * 1000;
        res += board[0][1] * 10000;
        res += board[0][0] * 100000;
        return res;
    }

    private int[][] intToBoard(int board) {
        int[][] res = new int[2][3];
        res[1][2] = board % 10;
        res[1][1] = (board / 10) % 10;
        res[1][0] = (board / 100) % 10;
        res[0][2] = (board / 1000) % 10;
        res[0][1] = (board / 10000) % 10;
        res[0][0] = board / 100000;
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] b1 = {{1, 2, 3}, {4, 0, 5}};
        int[][] b2 = {{4, 1, 2}, {5, 0, 3}};
        System.out.println(solution.slidingPuzzle(b1));
        System.out.println(solution.slidingPuzzle(b2));
    }
}
